翻訳と辞書 Words near each other ・ Tournado (The All-American Rejects album) ・ Tournafulla ・ Tournai ・ Tournai (constituency) ・ Tournai Cathedral ・ Tournai font ・ Tournai Mass ・ Tournai Phoenix ・ Tournai railway station ・ Tournai-sur-Dive ・ Tournaig ・ Tournaisian ・ Tournaisis ・ Tournament ・ Tournament (disambiguation) ・ Tournament (graph theory) ・ Tournament (medieval) ・ Tournament (solitaire) ・ Tournament Capital Centre ・ Tournament director ・ Tournament director (poker) ・ Tournament In Management and Engineering Skills ・ Tournament in Łukasz Romanek Memory ・ Tournament of Bands ・ Tournament of Champions ・ Tournament of Champions (debate) ・ Tournament of Champions (NJSIAA) ・ Tournament of Champions (squash) ・ Tournament of Champions (tennis) ・ Tournament of Champions 2011 Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Tournament (graph theory) ： ウィキペディア英語版 Tournament (graph theory) A tournament is a directed graph (digraph) obtained by assigning a direction for each edge in an undirected complete graph. That is, it is an orientation of a complete graph, or equivalently a directed graph in which every pair of distinct vertices is connected by a single directed edge. Many of the important properties of tournaments were first investigated by Landau in order to model dominance relations in flocks of chickens. Current applications of tournaments include the study of voting theory and social choice theory among other things. The name ''tournament'' originates from such a graph's interpretation as the outcome of a round-robin tournament in which every player encounters every other player exactly once, and in which no draws occur. In the tournament digraph, the vertices correspond to the players. The edge between each pair of players is oriented from the winner to the loser. If player $a$ beats player $b$, then it is said that $a$ ''dominates'' $b$. == Paths and cycles == Any tournament on a finite number $n$ of vertices contains a Hamiltonian path, i.e., directed path on all $n$ vertices (Rédei 1934). This is easily shown by induction on $n$: suppose that the statement holds for $n$, and consider any tournament $T$ on $n+1$ vertices. Choose a vertex $v\_0$ of $T$ and consider a directed path $v\_1,v\_2,\backslash ldots,v\_n$ in $T\backslash setminus\; \backslash$. Now let $i\; \backslash in\; \backslash$ be maximal such that for every $j\; \backslash leq\; i$ there is a directed edge from $v\_j$ to $v\_0$. ::$v\_1,\backslash ldots,v\_i,v\_0,v\_,\backslash ldots,v\_n$ is a directed path as desired. This argument also gives an algorithm for finding the Hamiltonian path. More efficient algorithms, that require examining only $\backslash \; O(n\; \backslash log\; n)$ of the edges, are known.〔.〕 This implies that a strongly connected tournament has a Hamiltonian cycle (Camion 1959). More strongly, every strongly connected tournament is vertex pancyclic: for each vertex ''v'', and each ''k'' in the range from three to the number of vertices in the tournament, there is a cycle of length ''k'' containing ''v''.〔, Theorem 1.〕 Moreover, if the tournament is 4‑connected, each pair of vertices can be connected with a Hamiltonian path (Thomassen 1980). 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Tournament (graph theory)」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.